package stmo.链表;

public class CircleListCheckInTest {


    /**
     *  快慢指针判断链表是否有环问题
     */

    public static void main(String[] args) {

        //创建结点
        Node<String> first = new Node<String>("aa",null);
        Node<String> second = new Node<String>("bb",null);
        Node<String> third = new Node<String>("cc",null);
        Node<String> fourth = new Node<String>("dd",null);
        Node<String> fifth = new Node<String>("ee",null);
        Node<String> six = new Node<String>("ff",null);
        Node<String> seven = new Node<String>("gg",null);

        //完成结点之间的指向
        first.next = second;
        second.next = third;
        third.next = fourth;
        fourth.next = fifth;
        fifth.next = six;
        six.next = seven;

        //产生环
        seven.next = third;

        Node<String> entrance = getEntrance(first);
        System.out.println("first链表中环的入口结点元素为："+entrance.item);
    }

    private static Node<String> getEntrance(Node<String> first) {
        //定义快慢指针
        Node fast = first;
        Node slow = first;
        Node temp = null;
        //遍历链表，先找到环(快慢指针相遇)，准备一个临时指针，指向链表的首结点，
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                temp = first;
                continue;
            }
            if(temp != null) {
                temp = temp.next;
                if (temp == slow) {
                    break;
                }
            }
        }
        //继续遍历，直到满指针和临时指针相遇，那么相遇时所指向的结点就是环的入口
        return temp;

    }


    private static class Node<T> {

        T item;

        Node next;

        public Node(T item, Node next) {

            this.item = item;
            this.next = next;
        }
    }

}
